from typing import List


class Solution:
    # 对于每一个房屋，我们有两种选择：偷它或者不偷它。因此我们维护一个动态规划
    # 的数组，大小为 2*n，第一行代表 NotRob(i) 不偷当前房屋的累计最大值，第二
    # 行 Rob(i) 代表偷当前房屋的累计最大值。由此我们可以写出状态转移方程：
    #     Rob(i) = NotRob(i-1) + nums[i]
    #     NotRob(i) = max(NotRob(i-1), Rob(i-1))
    # 最终答案即是 NotRob(n-1) 和 Rob(n-1) 的最大值。
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        rob, notRob = nums[0], 0

        for i in range(1, n):
            rob, notRob = notRob + nums[i], max(rob, notRob)
        
        return max(rob, notRob)
    
    # 213. 打家劫舍 II
    # https://leetcode.cn/problems/house-robber-ii/
    # 房屋呈环形
    # 环状排列意味着第一个房子和最后一个房子中只能选择一个偷窃
    # 在不偷窃第一个房子的情况下 (nums[1:])，最大金额是 p_1
    # 在不偷窃最后一个房子的情况下 (nums[:n-1])，最大金额是 p_2
    # 取两者最大值
    def rob2(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 3: return max(nums)

        def robHelper(start, end):
            # computes the rob sum within [start, end]
            rob, notRob = nums[start], 0
            for i in range(start+1, end+1):
                rob, notRob = notRob + nums[i], max(rob, notRob)
            return max(rob, notRob)
        
        return max(robHelper(0, n-2), robHelper(1, n-1))
